package algorithms.question.class16;

import common.util.MyUtil;

/**
 * https://leetcode-cn.com/problems/patching-array/
 *
 * @author guichang
 * @date 2021/8/15
 */

@SuppressWarnings("all")
public class Code3_按要求补齐数组 {

    public static void main(String[] args) {
        int[] arr = MyUtil.createArray(1, 5, 10);
        MyUtil.print(minPatches(arr, 20)); // 10
    }

    public static int minPatches(int[] nums, int n) {
        if (nums == null || nums.length == 0 || n <= 0) {
            return -1;
        }
        // 次数
        int patch = 0;
        // 当前最长的路径，防溢出要定义成long类型
        long range = 0;
        // 如果nums没有排序则此处需要排序
        for (int i = 0; i < nums.length; i++) {
            while (range + 1 < nums[i]) {
                range += range + 1;
                patch++;
                if (range >= n) {
                    return patch;
                }
            }
            // 到此处 1-(nums[i]-1)的路径已经搞定了
            range += nums[i];
            if (range >= n) {
                return patch;
            }
        }
        // 跳出循环还是没搞定n，需要继续延申
        while (range + 1 < n) {
            range += range + 1;
            patch++;
        }
        return patch;
    }

}